<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <script>
    // 请你设计并实现一个满足LRU（最近最少使用）缓存约束的数据结构 LRUCache（int
    //   capacity）以正整数作为容器 capacity初始化LRU缓存 int get（int key）如果关键字key存在缓存中，则返回关键字的值，否则返回-1
    // void put（int key， int value） 如果关键字key已经存在，则变更其数据值的value；如果不存在，则向缓存中插入该组key， value
    // 如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字 函数get和put 必须以0（1）的平均时间复杂度运行
    class LRUCache {
      constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
      }

      get(key) {
        if (this.cache.has(key)) {
          const value = this.cache.get(key);
          this.cache.delete(key);
          this.cache.set(key, value);
          return value;
        }
        return -1;
      }

      getCache() {
        return this.cache;
      }

      put(key, value) {
        if (this.cache.has(key)) {
          this.cache.delete(key);
        }
        this.cache.set(key, value);

        if (this.cache.size > this.capacity) {
          const deleteCacheKey = this.cache.keys().next().value;
          this.cache.delete(deleteCacheKey);
        }
      }
    }

    const cache = new LRUCache(2);
    cache.put(1, 'xxx');
    cache.put(5, 'yyy');
    cache.get(1);
    console.log(cache.getCache());
    cache.put(3, 'ddd');
    console.log(cache.getCache());

    class Node {
      constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
      }
    }
    class CacheLru {
      constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();

        this.head = new Node(null, null);
        this.tail = new Node(null, null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
      }

      get(key) {
        if (this.cache.has(key)) {
          const node = this.cache.get(key);
          this._remove(node);
          this._add(node);
          return node.value;
        }
        return -1;
      }

      put(key, value) {
        if (this.cache.has(key)) {
          this.remove(this.cache.get(key));
        }

        const node = new Node(key, value);
        this.cache.set(key, node);
        this._add(node);

        if (this.cache.size > this.capacity) {
          const deleteCache = this.head.next;
          this._remove(deleteCache);
          this.cache.delete(deleteCache.key);
        }
      }

      getCache() {
        const values = [];
        let current = this.head.next;
        while (current !== this.tail) {
          values.push(current.key);
          current = current.next;
        }

        return values;
      }

      _remove(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
      }

      _add(node) {
        node.prev = this.tail.prev;
        node.next = this.tail;
        this.tail.prev.next = node;
        this.tail.prev = node;
      }
    }

    const cacheLru = new CacheLru(2);
    cacheLru.put(1, 'xxx');
    cacheLru.put(5, 'yyy');
    cacheLru.get(1);
    console.log(cacheLru.getCache(), 'cacheLru');
    cacheLru.put(3, 'ddd');
    console.log(cacheLru.getCache());
  </script>
  <body>
   <div>纯map实现代码比较简洁，适合快速答题和快速实现</div>
   <div>链表方按不依赖语言特性，和支持扩展功能，可以扩展为LFU</div>
   <div>为什么需要双向链表，因为单链表无法再o1的时间内删除节点（要遍历找前驱节点）</div>
  </body>
</html>
